package 数组;

/**
 * https://leetcode.cn/problems/find-the-duplicate-number/
 *
 * https://leetcode.cn/problems/find-the-duplicate-number/solutions/58841/287xun-zhao-zhong-fu-shu-by-kirsche/
 *
 * 使用快慢指针的方式来解
 */
public class _287_寻找重复数 {

    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;

        slow = nums[slow];
        fast = nums[nums[fast]];

        while (fast != slow) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        int pre1 = 0;
        int pre2 = slow;

        while (pre1 != pre2) {
            pre1 = nums[pre1];
            pre2 = nums[pre2];
        }

        return pre1;
    }
}
